#include "bits/stdc++.h"
using namespace std;

const int maxr=1e5+10;
const int maxn=1e5+10;
int n,monster[maxn],ha[maxr],rec[maxn],l,b[maxn],ans,ese;

int main()
{
	freopen("duel.in","r",stdin);
	freopen("duel.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>monster[i];
		rec[i]=monster[i];
	}
	sort(monster+1,monster+1+n);
	l=unique(monster+1,monster+1+n)-monster-1;
	for(int i=1;i<=n;i++)
	{
		int p=upper_bound(monster+1,monster+1+l,rec[i])-monster-1;
		b[i]=p;
		ha[p]++;
	}
	sort(b+1,b+1+n);
	//wan cheng li san hua he pai xv
//	cout<<"b[i]:";
//	for(int i=1;i<=n;i++) cout<<b[i]<<" ";
//	cout<<endl;
//	for(int i=1;i<=l;i++) cout<<ha[i]<<" "; 
//	cout<<endl;
	int pos1=n;
	int pos2=n-(n/2);
	
//	cout<<"test"<<endl;
//	for(int i=49998;i<=50002;i++) cout<<b[i]<<" ";
//	cout<<endl;
	
	while(1)
	{
		if(pos1==n-n/2||pos2==0) break;
//		cout<<b[pos1]<<" "<<b[pos2]<<endl;
		if(b[pos1]>b[pos2])
		{
			ans++;
			pos1--;
			pos2--;
		}
		if(b[pos1]==b[pos2]) 
		{
			pos2--;
		}
		if(b[pos1]<b[pos2])break;
	}
//	cout<<pos1<<" "<<pos2<<endl; 
//	cout<<"1:"<<ans<<endl;
	if(pos1==n-n/2&&pos2==0)
	{
		cout<<n-ans<<endl;
		return 0;
	}
	int tmp=pos2;
	for(ese=n-n/2;ese>tmp;)
	{
//		cout<<"pos2:"<<pos2<<" ese:"<<ese<<endl;
		if(pos2==0||b[ese]<=b[pos2]||ese==tmp) break;
		if(b[ese]>b[pos2])
		{
			ese--;
			pos2--;
		}
	}
//	cout<<"end ese:"<<ese<<endl;
	ese=n-n/2-ese;
	ans+=ese;
	cout<<n-ans<<endl;
	return 0;
}
